package esercitazione2;

public class CountingSort implements Sorting{
	public int[] sort(int[] input) {
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		int length = 0;
		int[] tmp;
		int[] output = new int[input.length];

		if (input.length > 0) {
			for (int i : input) {
				if (i > max)
					max = i;
				if (i < min)
					min = i;
			}
			
			System.out.println("Min: " + min + "\tMax: " + max);
			
			length = max - min + 1;
			tmp = new int[length];
			
			for (int i : input) {
				tmp[i-min]++;
			}
			
			System.out.print("TMP COUNT   : { ");
			for (int i : tmp)
				System.out.print(i + " ");
			System.out.println("}");
			
			for (int index = 0; index < length; index++) {
				if(index == 0)
					tmp[index] = tmp[index] - 1;
				else
					tmp[index] = tmp[index] + tmp[index - 1];
			}
			
			System.out.print("TMP POSITION: { ");
			for (int i : tmp)
				System.out.print(i + " ");
			System.out.println("}");
			
			for (int index = input.length - 1; index >= 0; index--){
				output[tmp[input[index]-min]] = input[index];
				tmp[input[index]-min]--;
			}
		}
		return output;
	}
}
